class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        if(grid.size() < 1)  return 0;
        /*
        利用递归实现动态规划解决最优解问题:时间复杂度过高，递归中存在大量重复计算
        */
        vector<int> result;//存储可能的结果
        int iLength = grid.size();
        int jLength = grid[0].size();
        travel(grid, result, 0, 0, 0, iLength, jLength);

        int max = 0;
        for(int x : result)
        {
            if(x > max)  max = x;
        }

        return max;
    }

    void travel(vector<vector<int>>& grid, vector<int>& result, int sum, int i, int j, int& iLength, int& jLength){
        //sum表示当前路径和,i、j表示当前位置
        if(i > iLength - 1 || j > jLength - 1)  return;
        if(i == iLength - 1 && j == jLength - 1)
        {
            sum += grid[i][j];
            result.push_back(sum);
            return;
        }

        sum += grid[i][j];
        travel(grid, result, sum, i + 1, j, iLength, jLength);//向下递归
        travel(grid, result, sum, i, j + 1, iLength, jLength);//向右递归
        return;
    }

};

/*********************************************************************************************/
class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        if(grid.size() < 1)  return 0;
        /*
        （剑指）采用基于循环的代码能显著提高效率：需要一个二维数组用以表示到达当前空格时能收到礼物的最大值；
        到达(i, j)有两个方向，由上（up）而下或由左（left）至右
        */
        int rows = grid.size();
        int cols = grid[0].size();
        vector<vector<int>> maxValues;
        for(int i = 0; i < rows; ++i)  maxValues.push_back(vector<int>(cols));

        for(int i = 0; i < rows; ++i)
        {
            for(int j = 0; j < cols; ++j)
            {
                int up = 0;
                int left = 0;

                if(i > 0)  up = maxValues[i - 1][j];
                if(j > 0)  left = maxValues[i][j - 1];

                maxValues[i][j] = max(left, up) + grid[i][j];
            }
        }

        return maxValues[rows - 1][cols - 1];
    }

};

/**************************************************************************************************/
class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        if(grid.size() < 1)  return 0;
        /*
        利用递归实现动态规划解决最优解问题:时间复杂度O(n*m)过高;
        （剑指）采用基于循环的代码能显著提高效率：需要一个二维数组用以表示到达当前空格时能收到礼物的最大值；
        到达(i, j)有两个方向，由上（up）而下或由左（left）至右;
        进一步优化：由于(i, j)坐标点的值仅仅依赖当前行及第i - 1行值，所以没必要保存第i - 2行及更上面的行
        */
        int rows = grid.size();
        int cols = grid[0].size();
        vector<int> maxValues(cols, 0);//使用一个数组即可

        for(int i = 0; i < rows; ++i)
        {
            for(int j = 0; j < cols; ++j)
            {
                int up = 0;
                int left = 0;

                if(i > 0)  up = maxValues[j];
                if(j > 0)  left = maxValues[j - 1];

                maxValues[j] = max(left, up) + grid[i][j];
            }
        }

        return maxValues[cols - 1];
    }

};